#include "regEx.h"
regExprHandler::regExprHandler()
{
	m_nNextStateID	= 0;
}

regExprHandler::~regExprHandler()
{
	CleanUp();
}

bool regExprHandler::SetRegEx(string strRegEx)
{
	CleanUp();
	if(!CreateNFA(strRegEx))
		return false;
	ConvertNFAtoDFA();
	ReduceDFA();
      	return true;
}

bool regExprHandler::FindFirst(string strText, int &nPos, string &strPattern)
{
	list<CAG_PatternState*>::iterator iter;
	for(iter=m_PatternList.begin(); iter!=m_PatternList.end(); ++iter)
		delete *iter;
	m_PatternList.clear();
	m_strText			= strText;
	if(Find())
	{
		nPos			= m_vecPos[0];
		strPattern		= m_vecPattern[0];
		m_nPatternIndex	= 0;
		return true;
	}
	return false;
}

bool regExprHandler::FindNext(int &nPos, string &strPattern)
{
	++m_nPatternIndex;
	if(m_nPatternIndex<m_vecPos.size())
	{
		nPos			= m_vecPos[m_nPatternIndex];
		strPattern		= m_vecPattern[m_nPatternIndex];
		return true;
	}
	return false;
}

bool regExprHandler::Find()
{
	bool bRes = false;
	m_vecPos.clear();
	m_vecPattern.clear();
	if(m_DFATable.empty())
		return false;
	for(int i=0; i<m_strText.size(); ++i)
	{
		char c = m_strText[i];
		list<CAG_PatternState*>::iterator iter;
		for(iter=m_PatternList.begin(); iter != m_PatternList.end(); iter++)
		{
			CAG_PatternState *pPatternState = *iter;
			vector<expState*> Transition; // must be at most one because this is DFA
			pPatternState->m_pState->GetTransition(c, Transition);
			if(!Transition.empty())
			{
				pPatternState->m_pState = Transition[0];
				if(Transition[0]->acceptingState_)
				{
					m_vecPos.push_back(pPatternState->m_nStartIndex);
					m_vecPattern.push_back(m_strText.substr(pPatternState->m_nStartIndex, 
						i-pPatternState->m_nStartIndex+1));
				}
			}
			else
			{
				iter = m_PatternList.erase(iter);
				if(iter == m_PatternList.end())break;
				//--iter;
			}
			
		}
		expState *pState = m_DFATable[0];
		vector<expState*> Transition;
		pState->GetTransition(c, Transition);
		if(!Transition.empty())
		{
			CAG_PatternState *pPatternState = new CAG_PatternState();
			pPatternState->m_nStartIndex	= i;
			pPatternState->m_pState			= Transition[0];
			m_PatternList.push_back(pPatternState);
			if(Transition[0]->acceptingState_)
			{
				m_vecPos.push_back(i);
				string strTemp;
				strTemp += c;
				m_vecPattern.push_back(strTemp);
			}
		}
		else
		{
			if(pState->acceptingState_)
			{
				m_vecPos.push_back(i);
				string strTemp;
				strTemp += c;
				m_vecPattern.push_back(strTemp);
			}
		}
	}
	return(m_vecPos.size()>0);
}

bool regExprHandler::Eval()
{
	if(m_OperatorStack.size()>0)
	{
		char chOperator = m_OperatorStack.top();
		m_OperatorStack.pop();
		switch(chOperator)
		{
		case  42:
			return Star();
			break;
		case 124:
			return Union();
			break;
		case   8:
			return Concat();
			break;
		}

		return false;
	}

	return false;
}

bool regExprHandler::Concat()
{
	FSA_TABLE A, B;
	if(!Pop(B) || !Pop(A))
		return false;
	A[A.size()-1]->AddTransition(0, B[0]);
	A.insert(A.end(), B.begin(), B.end());
	m_OperandStack.push(A);
	return true;
}

bool regExprHandler::Star()
{
	FSA_TABLE A, B;
	if(!Pop(A))
		return false;
	expState *pStartState	= new expState(++m_nNextStateID);
	expState *pEndState	= new expState(++m_nNextStateID);
	pStartState->AddTransition(0, pEndState);
	pStartState->AddTransition(0, A[0]);
	A[A.size()-1]->AddTransition(0, pEndState);
	A[A.size()-1]->AddTransition(0, A[0]);
	A.push_back(pEndState);
	A.push_front(pStartState);
	m_OperandStack.push(A);
	return true;
}

bool regExprHandler::Union()
{
	FSA_TABLE A, B;
	if(!Pop(B) || !Pop(A))
		return false;
	expState *pStartState	= new expState(++m_nNextStateID);
	expState *pEndState	= new expState(++m_nNextStateID);
	pStartState->AddTransition(0, A[0]);
	pStartState->AddTransition(0, B[0]);
	A[A.size()-1]->AddTransition(0, pEndState);
	B[B.size()-1]->AddTransition(0, pEndState);
	B.push_back(pEndState);
	A.push_front(pStartState);
	A.insert(A.end(), B.begin(), B.end());
	m_OperandStack.push(A);
	return true;
}

string regExprHandler::ConcatExpand(string strRegEx)
{
	string strRes;
	for(int i=0; i<strRegEx.size()-1; ++i)
	{
		char cLeft	= strRegEx[i];
		char cRight = strRegEx[i+1];
		strRes	   += cLeft;
		if((IsInput(cLeft)) || (IsRightParanthesis(cLeft)) || (cLeft == '*'))
			if((IsInput(cRight)) || (IsLeftParanthesis(cRight)))
				strRes += char(8);
	}
	strRes += strRegEx[strRegEx.size()-1];
	return strRes;
}

bool regExprHandler::CreateNFA(string strRegEx)
{
	strRegEx = ConcatExpand(strRegEx);
	for(int i=0; i<strRegEx.size(); ++i)
	{
		char c = strRegEx[i];
		if(IsInput(c))
			Push(c);
		else if(m_OperatorStack.empty())
			m_OperatorStack.push(c);
		else if(IsLeftParanthesis(c))
			m_OperatorStack.push(c);
		else if(IsRightParanthesis(c))
		{
			while(!IsLeftParanthesis(m_OperatorStack.top()))
				if(!Eval())
					return false;
			m_OperatorStack.pop(); 
		}
		else
		{
			while(!m_OperatorStack.empty() && Presedence(c, m_OperatorStack.top()))
				if(!Eval())
					return false;
			m_OperatorStack.push(c);
		}
	}
	while(!m_OperatorStack.empty())
		if(!Eval())
			return false;
	if(!Pop(m_NFATable))
		return false;
	m_NFATable[m_NFATable.size()-1]->acceptingState_ = true;

	return true;
}

void regExprHandler::Push(char chInput)
{
	expState *s0 = new expState(++m_nNextStateID);
	expState *s1 = new expState(++m_nNextStateID);
	s0->AddTransition(chInput, s1);
	FSA_TABLE NFATable;
	NFATable.push_back(s0);
	NFATable.push_back(s1);
	m_OperandStack.push(NFATable);
	m_InputSet.insert(chInput);
}

bool regExprHandler::Pop(FSA_TABLE &NFATable)
{
	if(m_OperandStack.size()>0)
	{
		NFATable = m_OperandStack.top();
		m_OperandStack.pop();
		return true;
	}

	return false;
}

void regExprHandler::EpsilonClosure(set<expState*> T, set<expState*> &Res)
{
	Res.clear();
	Res = T;
	stack<expState*> unprocessedStack;
	set<expState*>::iterator iter;
	for(iter=T.begin(); iter!=T.end(); ++iter)
		unprocessedStack.push(*iter);
	while(!unprocessedStack.empty())
	{
		expState* t = unprocessedStack.top();
		unprocessedStack.pop();
		vector<expState*> epsilonStates;
		t->GetTransition(0, epsilonStates);
		for(int i=0; i<epsilonStates.size(); ++i)
		{
			expState* u = epsilonStates[i];
			if(Res.find(u) == Res.end())
			{
				Res.insert(u);
				unprocessedStack.push(u);
			}
		}
	}
}

void regExprHandler::Move(char chInput, set<expState*> T, set<expState*> &Res)
{
	Res.clear();
	set<expState*>::iterator iter;
	for(iter=T.begin(); iter!=T.end(); ++iter)
	{
		expState* pState = *iter;
		vector<expState*> States;
		pState->GetTransition(chInput, States);
		for(int i=0; i<States.size(); ++i)
			Res.insert(States[i]);
	}
}

void regExprHandler::ConvertNFAtoDFA()
{
	for(int i=0; i<m_DFATable.size(); ++i)
		delete m_DFATable[i];
	m_DFATable.clear();
	if(m_NFATable.size() == 0)
		return;
	m_nNextStateID = 0;
	vector<expState*> unmarkedStates;
	set<expState*> DFAStartStateSet;
	set<expState*> NFAStartStateSet;
	NFAStartStateSet.insert(m_NFATable[0]);
	EpsilonClosure(NFAStartStateSet, DFAStartStateSet);
	expState *DFAStartState = new expState(DFAStartStateSet, ++m_nNextStateID);
	m_DFATable.push_back(DFAStartState);
	unmarkedStates.push_back(DFAStartState);
	while(!unmarkedStates.empty())
	{
		expState* processingDFAState = unmarkedStates[unmarkedStates.size()-1];
		unmarkedStates.pop_back();
		set<char>::iterator iter;
		for(iter=m_InputSet.begin(); iter!=m_InputSet.end(); ++iter)
		{
			set<expState*> MoveRes, EpsilonClosureRes;
			Move(*iter, processingDFAState->GetNFAState(), MoveRes);
			EpsilonClosure(MoveRes, EpsilonClosureRes);
			bool bFound		= false;
			expState *s	= NULL;
			for(int i=0; i<m_DFATable.size(); ++i)
			{
				s = m_DFATable[i];
				if(s->GetNFAState() == EpsilonClosureRes)
				{
					bFound = true;
					break;
				}
			}
			if(!bFound)
			{
				expState* U = new expState(EpsilonClosureRes, ++m_nNextStateID);
				unmarkedStates.push_back(U);
				m_DFATable.push_back(U);
				processingDFAState->AddTransition(*iter, U);
			}
			else
			{
				processingDFAState->AddTransition(*iter, s);
			}
		}
	}
}

void regExprHandler::ReduceDFA()
{
	set<expState*> DeadEndSet;
	for(int i=0; i<m_DFATable.size(); ++i)
		if(m_DFATable[i]->IsDeadEnd())
			DeadEndSet.insert(m_DFATable[i]);
	if(DeadEndSet.empty())
		return;
	set<expState*>::iterator iter;
	for(iter=DeadEndSet.begin(); iter!=DeadEndSet.end(); ++iter)
	{
		for(int i=0; i<m_DFATable.size(); ++i)
			m_DFATable[i]->RemoveTransition(*iter);
		deque<expState*>::iterator pos;
		for(pos=m_DFATable.begin(); pos!=m_DFATable.end(); ++pos)
			if(*pos == *iter)
				break;
		m_DFATable.erase(pos);
		delete *iter;
	}
}
